#ifndef HashDict_h__
#define HashDict_h__


namespace inf {

    template<typename Type>
    class HashDict {
    public:
        HashDict();

        void		clear( void );							// clear All Entries

        void		set_granularity( int granularity );		// set the granularity

        int			size( void ) const;						// Number of used entries
        void		remove( const char *key );				// remove an item (list won't be resized).
        void		remove( int index );					// remove an item (list won't be resized).

        void		copy( const HashDict<Type> &other );		// clear dict and copy from all keyvalues from other
        void        merge( const HashDict<Type> &other, bool overWrite );	// copy from all keyvalues from other, overwriting existing or leaving them

        const Str&  get_key( int index ) const;				// get they key of an item

        // find functions
        int			find( const char *key, bool casesensitive = true ) const;
        int			match_prefix( const char *prefix, int length, int prevMatch=-1 ) const;

        // operators
        const Type &operator[]( const char *key ) const;	// get the specified item
        Type &		operator[]( const char *key );			// get the specified item
        const Type &operator[]( int index ) const;			// get the specified item
        Type &		operator[]( int index );				// get the specified item

        const List<Type>&   GetEntries() const { return entries; }

        HashDict<Type> &operator=( const HashDict<Type> &other );

    protected:
        List<Type>	    entries;
        StrList     	names;
        HashIndex	    hashIndex;
    };

    /*
    ================
    HashDict::HashDict
    ================
    */
    template<typename Type>
    HashDict<Type>::HashDict() {
        set_granularity(16);
    }

    /*
    ================
    HashDict::clear
    ================
    */
    template<typename Type>
    void HashDict<Type>::clear( void ) {
        entries.clear();
        names.clear();
        hashIndex.clear();
    }

    /*
    ================
    HashDict::set_granularity
    ================
    */
    template<typename Type>
    void HashDict<Type>::set_granularity( int granularity ) {
        entries.set_granularity( granularity );
        names.set_granularity( granularity );
    }

    /*
    ================
    HashDict::size
    ================
    */
    template<typename Type>
    int HashDict<Type>::size( void ) const {
        return entries.size();
    }

    /*
    ================
    HashDict::remove
    ================
    */
    template<typename Type>
    void HashDict<Type>::remove( const char *key ) {
        int hash = hashIndex.generate_key( key, false );
        for( int i=hashIndex.get_first(hash); i!=HashIndex::NULL_INDEX; i=hashIndex.get_next(i) ) {
            if ( names[i].cmp( key, false) == 0 ) {
                entries.remove( i );
                names.remove( i );
                hashIndex.remove( hash, i );
                return;
            }
        }
    }

    /*
    ================
    HashDict::remove
    ================
    */
    template<typename Type>
    void HashDict<Type>::remove( int index ) {
        assert( index >= 0 && index <= entries.size() );

        hashIndex.remove( hashIndex.generate_key( names[index].c_str(), false ), index );
        entries.remove_index( index );
        names.remove_index( index );
    }

    /*
    ================
    HashDict::copy
    ================
    */
    template<typename Type>
    void HashDict<Type>::copy( const HashDict<Type> &other ) {
        clear();
        int num = other.entries.size();
        for ( int i = 0; i < num; i++ ) {
            const Str &key = other.get_key(i);
            hashIndex.add( hashIndex.generate_key( key.c_str(), false ), entries.size() );
            names.append( key );
            entries.append( other[i] );
        }
    }

    /*
    ================
    HashDict::merge
    ================
    */
    template<typename Type>
    void HashDict<Type>::merge( const HashDict<Type> &other, bool overWrite ) {
        const char *key;
        int index;
        int num = other.entries.size();
        for ( int i = 0; i < num; i++ ) {
            const Str &key = other.get_key(i);
            index = find( key.c_str() );
            if ( index != HashIndex::NULL_INDEX ) {
                if ( overWrite )
                    entries[index] = other[i];
                continue;
            }
            hashIndex.add( hashIndex.generate_key( key.c_str(), false ), entries.size() );
            names.append( key );
            entries.append( other[i] );
        }
    }

    /*
    ================
    HashDict::get_key
    ================
    */
    template<typename Type>
    const Str& HashDict<Type>::get_key( int index ) const {
        assert( index >= 0 && index <= entries.size() );
        return names[index];
    }

    /*
    ================
    HashDict::find
    ================
    */
    template<typename Type>
    int HashDict<Type>::find( const char *key, bool casesensitive ) const {
        if ( key == NULL || key[0] == '\0' )
            return HashIndex::NULL_INDEX;

        int hash = hashIndex.generate_key( key, false );
        for ( int i = hashIndex.get_first( hash ); i != HashIndex::NULL_INDEX; i = hashIndex.get_next(i) ) {
            if ( names[i].cmp( key, casesensitive ) == 0 )
                return i;
        }

        return HashIndex::NULL_INDEX;
    }

    /*
    ================
    HashDict::match_prefix
    ================
    */
    template<typename Type>
    int HashDict<Type>::match_prefix( const char *prefix, int length, int prevMatch ) const {
        if ( prefix == NULL || prefix[0] == '\0' )
            return HashIndex::NULL_INDEX;

        int num = entries.size();
        for( int i=prevMatch+1; i<num; i++ ) {
            if ( !names[i].cmpn( prefix, length, false ) )
                return i;
        }
        return HashIndex::NULL_INDEX;
    }

    /*
    ================
    HashDict::operator[const char *]
    ================
    */
    template<typename Type>
    const Type &HashDict<Type>::operator[]( const char *key ) const {
        int index = find( key );
        if ( index != HashIndex::NULL_INDEX )
            return entries[index];

        // Not found, create one
        hashIndex.add( hashIndex.generate_key( key, false ), entries.size() );
        names.append(key);
        return entries.alloc_to_back();
    }

    template<typename Type>
    Type &HashDict<Type>::operator[]( const char *key ) {
        int index = find( key );
        if ( index != HashIndex::NULL_INDEX )
            return entries[index];

        // Not found, create one
        hashIndex.add( hashIndex.generate_key( key, false ), entries.size() );
        names.append(key);
        return entries.alloc_to_back();
    }

    /*
    ================
    HashDict::operator[int]
    ================
    */
    template<typename Type>
    const Type &HashDict<Type>::operator[]( int index ) const {
        assert( index >= 0 && index <= entries.size() );
        return entries[index];
    }
    template<typename Type>
    Type &HashDict<Type>::operator[]( int index ) {
        assert( index >= 0 && index <= entries.size() );
        return entries[index];
    }

    /*
    ================
    HashDict::operator=
    ================
    */
    template<typename Type>
    HashDict<Type> &HashDict<Type>::operator=( const HashDict<Type> &other ) {
        copy( other );
        return *this;
    }

}   // ::inf

#endif // HashDict_h__
